【算法题】服务器广播

共计 1455 个字符，预计需要花费 4 分钟才能阅读完成。

题目描述

服务器连接方式包括直接连接，间接连接。A和B直接连接，B和C直接连接，则A和C间接连接。直接连接和间接连接都可以发送广播。
给出一个NN数组，代表N个服务器，matrix[i][j] == 1，则代表i和j直接连接；不等于1时，代表i和j不直接连接。matrix[i][i] == 1，即自己和自己直接连接。matrix[i][j] == matrix[j][i]。
计算初始需要给几台服务器广播，才可以使每个服务器都收到广播。

题目要求

• 输入描述:
  输入为N行，每行有N个数字，为0或1，由空格分隔，构成N*N的数组，N的范围为 1<=N<=40
• 输出描述:
  输出一个数字，为需要广播的服务器的数量

示例1

输入
1 0 0
0 1 0
0 0 1
输出
3
说明
3台服务器互不连接，所以需要分别广播这3台服务器

示例2

输入
1 1
1 1
输出
1
说明
2台服务器相互连接，所以只需要广播其中一台服务器

JAVA解法

import java.util.*;

/**
 * @since 2022年4月20日
 */
public class ServerBroadcast {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] servers = scanner.nextLine().split(" ");
        int N = servers.length;
        int count = 0;
        int[][] arrServer = new int[N][N];
        for (int i = 0; i < N; i++) {
            arrServer[count][i] = Integer.parseInt(servers[i]);
        }
        while (++count < N) {
            servers = scanner.nextLine().split(" ");
            for (int i = 0; i < N; i++) {
                arrServer[count][i] = Integer.parseInt(servers[i]);
            }
        }

        // 打印一下二维数组
//        System.out.println(Arrays.deepToString(arrServer));

        Map<Integer, Set<Integer>> map = new HashMap<>();
        //把直接相连的服务器存储起来
        for (int i = 0; i < N; i++) {
            Set<Integer> set = new HashSet<>();
            for (int j = 0; j < N; j++) {
                boolean isSame = arrServer[i][j] == 1;
                if (isSame) {
                    set.add(j);
                    map.put(i, set);
                }
            }
        }
        //取出间接相连的
        for (Map.Entry<Integer, Set<Integer>> entry : map.entrySet()) {
            int key = entry.getKey();
            Set<Integer> broadcastSet = entry.getValue();
            for (Integer broadcast : broadcastSet) {
                if (key != broadcast) {
                    map.put(broadcast, broadcastSet);
                }
            }
        }

        Set<Set<Integer>> ret = new HashSet<>();
        for (Map.Entry<Integer, Set<Integer>> entry : map.entrySet()) {
            ret.add(entry.getValue());
        }
        System.out.println(ret.size());
    }
}